|
In graph theory, a continuous graph is a graph whose set of vertices is a continuous space ''X''. Continuous graphs are used as models for real-world graphs, as an alternative to other graph models such as for instance exponential random graph models. == Definition == Edges, being unordered pairs of vertices, are defined in a continuous graph by a symmetric relation (i.e. subset) of the cartesian product ''X''2 or equivalently by a symmetric function from ''X''2 to the set . This could represent 1 for an edge between two vertices, and 0 for no edge, or it could represent a complete graph with a 2-color edge coloring. In this context, the set is often denoted by 2, so we have f(''X''2)→2. For multi-colorings of edges we would have f(''X''2)→n. The value of the function f(x,y) for x=y, i.e. whether the relation is reflexive determines whether the graph has loops or not but this isn't usually considered as it doesn't make much difference to the theory.〔 In descriptive set theory the spaces of interest are perfect separable Polish spaces and related spaces. Given a finite graph H and a continuous or discrete graph G, the homomorphism density ''t(H,G)'' is defined to be the proportion of injective maps from the vertex set of H to vertex set of G which is a graph homomorphism. For instance, if H consists of two vertices joined by a single edge, ''t(H,G)'' is the edge density of G. A sequence of finite (dense) graphs ''Gn'' is said to be convergent if, for each fixed finite graph ''H'', the homomorphism densities ''t(H,Gn)'' are a convergent sequence of numbers. A continuous graph G is said to be a limit of such a sequence if ''t(H,Gn)'' converges to ''t(H,G)'' for each ''H'', in which case we refer to G as a graphon. Such a limit is a symmetric measurable function in two variables, that can often be written f(''X''2)→() which is the same as a complete continuous graph where the edges have values in the interval (). It can be shown that any sequence of dense graphs has a convergent subsequence, whose limit is a graphon which is unique up to measure rearrangement. A key tool used in the proof of this claim is the Szemerédi regularity lemma. For instance, for each natural number ''n'', let ''Gn'' be a complete bipartite graph between two sets of ''n'' vertices. Then in the limit , ''Gn'' converges to the graphon described by the function f(()2)→() defined by setting ''f(x,y)=1'' when , and ''f(x,y)=0'' otherwise. Graphons can be used to establish results in the property testing of graphs. For any sets X and Y, the two-variable symmetric function f(''X''2)→Y is a complete graph with edges labelled with elements of Y. For multi-variable symmetric functions we have f(''X''n)→Y for the complete hypergraph with edges labelled with elements of Y. Given a discrete-time dynamical system, the trajectories, or orbits (state space) of all the points form a (possibly disconnected) directed graph which is a continuous graph if the system is defined on a continuous space. The trajectories of a continuous-time dynamical system would form a collection of curved paths (phase space) rather than a collection of piece-wise linear paths and so is not a graph in the traditional sense. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Continuous graph」の詳細全文を読む スポンサード リンク
|